package leetcode_周赛._2022._202203;

import general_class.TreeNode;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/3/6 10:36
 */
public class _06 {
    public static void main(String[] args) {
        System.out.println(new _06().minimalKSum(new int[]{1}, 1000000000));
    }

    /**
     * 6016. Excel 表中某个范围内的单元格
     * 算法：模拟
     * @param s
     * @return
     */
    public List<String> cellsInRange(String s) {
        String[] split = s.split(":");
        char l1 = split[0].charAt(0), r1 = split[1].charAt(0);
        int l2 = split[0].charAt(1) - '0', r2 = split[1].charAt(1) - '0';
        List<String> ans = new ArrayList<>();
        for (char i = l1; i <= r1; i++) {
            for (int j = l2; j <= r2; j++) ans.add(i + ":" + j);
        }
        return ans;
    }

    /**
     * 6017. 向数组中追加 K 个整数
     * 算法：模拟
     * @param nums
     * @param k
     * @return
     */
    public long minimalKSum(int[] nums, int k) {
        long ans = 0;
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            long j = i == 0 ? 1 : nums[i - 1] + 1, tmp = nums[i] - j;
            if (tmp < 1) continue;
            if (tmp > k) tmp = k;
            ans += (j + nums[i] - 1) * tmp / 2;
            k -= tmp;
            if (k == 0) break;
        }
        if (k > 0) {
            long a = nums[len - 1] + 1, b = nums[len - 1] + k;
            ans += (a + b) * k / 2;
        }
        return ans;
    }

    /**
     * 6018. 根据描述创建二叉树
     * 算法：哈希表 + 队列
     * @param descriptions
     * @return
     */
    public TreeNode createBinaryTree(int[][] descriptions) {
        Map<Integer, List<int[]>> map = new HashMap<>();
        Set<Integer> set = new HashSet<>();
        for (int[] desc : descriptions) {
            List<int[]> list = map.getOrDefault(desc[0], new ArrayList<>());
            int[] nums = new int[2];
            nums[0] = desc[1];
            nums[1] = desc[2];
            list.add(nums);
            map.put(desc[0], list);
            set.add(desc[0]);
            set.add(desc[1]);
        }
        for (int[] desc : descriptions) set.remove(desc[1]);
        int parent = 0;
        for (Integer num : set) parent = num;
        Deque<TreeNode> queue = new ArrayDeque<>();
        TreeNode root = new TreeNode(parent);
        queue.addLast(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.pollFirst();
                if (node == null) continue;
                List<int[]> childs = map.getOrDefault(node.val, new ArrayList<>(0));
                if (childs.isEmpty()) continue;
                childs.sort(Comparator.comparingInt(a -> a[1]));
                for (int[] child : childs) {
                    if (child[1] == 1) {
                        node.left = new TreeNode(child[0]);
                        queue.addLast(node.left);
                    }
                    else {
                        node.right = new TreeNode(child[0]);
                        queue.addLast(node.right);
                    }
                }
            }
        }
        return root;
    }

}
